package Hard;

import java.util.*;

public class Solution1851 {
//    class IntervalsNode {
//        int val;
//        IntervalsNode next;
//
//        IntervalsNode(int val) {
//            val = this.val;
//            next = null;
//        }
//    }

    public int[] minInterval(int[][] intervals, int[] queries) {
        Map<Integer, TreeSet<Integer>> map = new TreeMap<Integer, TreeSet<Integer>>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            int length = right - left + 1;
            if (!map.containsKey(left)) {
                TreeSet<Integer> set = new TreeSet<Integer>(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1-o2;
                    }
                });
                set.add(length);
                map.put(left, set);
            } else {
                TreeSet set = map.get(left);
                set.add(length);
            }
        }
        Set<Integer> integers = map.keySet();
        Integer[] keys = integers.toArray(new Integer[integers.size()]);
        // 每次二分查找
        int[] ans = new int[queries.length];
        for(int i = 0 ; i < queries.length ; i++){
            int start = find(keys,queries[i]);
            if(start == -1){
                ans[i] = -1;
                continue;
            }else{
                int minLength = 10000001;
                for(int j = start ; j >=0 ; j--){
                    int key = keys[j];
                    TreeSet treeSet = map.get(key);
                    Object[] objects = treeSet.toArray(new Integer[treeSet.size()]);
                    for(int k = 0 ; k < objects.length ; k++){
                        if(key + (int)objects[k] - 1>= queries[i]){
                            minLength = Math.min(minLength,(int)objects[k]);
                            break;
                        }
                    }
//                    while(intervalsNode!=null){
//                        if(key + intervalsNode.val >= queries[i]){
//                            minLength = Math.min(minLength,intervalsNode.val);
//                            break;
//                        }
//                        intervalsNode = intervalsNode.next;
//                    }
                }
                if(minLength == 10000001){
                    ans[i] = -1; // 没找到
                }else{
                    ans[i] = minLength;
                }
            }
        }
        return ans;
    }

    public static int find(Integer[] keys, int target) {
        int i = 0;
        int j = keys.length - 1;
        while (i <= j) {
            int mid = (j - i) / 2 + i;
            if(keys[mid] == target){
                return mid;
            }else if(keys[mid] > target){
                j = mid - 1;
            }else{
                i = mid + 1;
            }
        }
        if(j == -1)
            return -1; // 如果这里返回-1，那么最终答案也一定为-1
        return i < j ? i : j; // 包含小的位置，因为上面是包含mid位置
    }
}
